package top100.dynamic;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/22 13:30
 * @description: 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
 * <p>
 * 测试用例保证结果在 32 位有符号整数范围内。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "rabbbit", t = "rabbit"
 * 输出：3
 * 解释：
 * 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
 * rabbbit
 * rabbbit
 * rabbbit
 * 示例 2：
 * <p>
 * 输入：s = "babgbag", t = "bag"
 * 输出：5
 * 解释：
 * 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length, t.length <= 1000
 * s 和 t 由英文字母组成
 */
public class Solution115 {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length()][t.length()];
        if (s.charAt(0) == t.charAt(0)) {
            dp[0][0] = 1;
        }
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == t.charAt(0)) {
                dp[i][0] = dp[i - 1][0] + 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int i = 1; i < s.length(); i++) {
            for (int j = 1; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                dp[i][j] += dp[i - 1][j];
            }
        }
        return dp[s.length() - 1][t.length() - 1];
    }

    public static void main(String[] args) {
        Solution115 solution = new Solution115();
        String s = "rabbbit";
        String t = "rabbit";
        int res = solution.numDistinct(s, t);
        System.out.println(res);
    }
}
